package hot100;

import java.io.StringReader;

public class d3_最小覆盖子串 {
    static class Result{
        int i,j;
        public Result(int i,int j){
            this.i = i;
            this.j = j;
        }
    }
    public String minWindow(String s, String t) {
        char[] target = t.toCharArray();
        int[] targetCount = new int[128];
        for (char c : target) {
            targetCount[c]++;
        }
        int pastTotal = 0;
        for(int count : targetCount){
            if(count > 0){
                pastTotal++;
            }
        }
        int pasted = 0;
        char[] source = s.toCharArray();
        int[] sourceCount = new int[128];
        int i = 0;
        int j = 0;
        Result res = null;
        while (j < source.length) {
            char right = source[j];
            sourceCount[right]++;
            if(sourceCount[right] == targetCount[right]){
                pasted++;
            }
            while (i<=j && pasted == pastTotal){
                if(res == null){
                    res = new Result(i,j);
                }else {
                    if(j - i < res.j - res.i){
                        res = new Result(i,j);
                    }
                }
                char left = source[i];
                sourceCount[left]--;
                if(sourceCount[left] < targetCount[left]){
                    pasted--;
                }
                i++;
            }
            j++;
        }
        return res == null ? "" : new String(source, res.i, res.j-res.i+1);
    }
}
